#include "testsetXor.h"
#include "Hadamard.h"
#include "global.h"
#include "LFSR.h"
#include<tuple>
#include<list>
#include<algorithm>
#include"function.h"
using namespace std;
testsetXor::testsetXor(void)
{
}
 
 
testsetXor::~testsetXor(void)
{
}

vector<int> testsetXor::_Choose(const string& pattern,const vector<string> hadamard)
{
	//tuple<positon,compitibility>
	vector<tuple<int,int>>  r;
	for(uint32_t i=0;i<hadamard.size();i++)
	{  
		int t;
		t=_CmpString(pattern,hadamard.at(i),[](const char& ch1,const char& ch2){
			if(ch1==ch2)return 1;
			return 0;});
			//if(t>compatibiliry)
			//{
				//compatibiliry=t;
				//reversed=false;
				//p=i;
			//}
			r.push_back(make_tuple(i,t));
			t=_CmpString(pattern,hadamard.at(i),[](const char& ch1,const char& ch2){
				if(ch1!=ch2&&ch1!='X')return 1;
				return 0;});
				//if(t>compatibiliry)
				//{
					//compatibiliry=t;
					//reversed=true;
					//p=i;
				//}
			r.push_back(make_tuple(i+hadamard.size(),t));	
	}
	//cout<<"["<<p<<","<<reversed<<"]\t";
	//cout<<p+1<<"  ";
	sort(r.begin(),r.end(),[](const tuple<int,int>& x,const tuple<int,int>& y){
	return get<1>(x)>get<1>(y);});
	int _c=get<1>(r.front());
	int i=0;
	vector<int> s;
	while(get<1>(r[i])>=_c)
	{
		//cout<<"["<<get<0>(r[i])<<","<<get<1>(r[i])<<"]\t";
		s.push_back(get<0>(r[i]));
		i++;
	}
	//cout<<endl;
	//return make_tuple(get<0>(r.front()),get<1>(r.front()));
	//random_shuffle(s.begin(),s.end());
	return s;
}
vector<int> testsetXor::_Choose_multi(const vector<string>&_set,int p,\
const vector<string> hadamard,int in_num)
{
	//tuple<positon,compitibility>
	int size=1<<in_num;
	vector<tuple<int,int>>  r;
	for(uint32_t i=0;i<hadamard.size();i++)
	{  
		int t1=0;
		int t2=0;
		for(int j=p;j<_set.size();j+=size){
		t1+=_CmpString(_set[j],hadamard.at(i),[](const char& ch1,const char& ch2){
			if(ch1==ch2)return 1;
			return 0;});
			//if(t>compatibiliry)
			//{
				//compatibiliry=t;
				//reversed=false;
				//p=i;
			//}
			//r.push_back(make_tuple(i,t));
			t2+=_CmpString(_set[j],hadamard.at(i),[](const char& ch1,const char& ch2){
				if(ch1!=ch2&&ch1!='X')return 1;
				return 0;});
				//if(t>compatibiliry)
				//{
					//compatibiliry=t;
					//reversed=true;
					//p=i;
				//}
				}
			r.push_back(make_tuple(i,t1));
			r.push_back(make_tuple(i+hadamard.size(),t2));	
	}
	//cout<<"["<<p<<","<<reversed<<"]\t";
	//cout<<p+1<<"  ";
	sort(r.begin(),r.end(),[](const tuple<int,int>& x,const tuple<int,int>& y){
	return get<1>(x)>get<1>(y);});
	int _c=get<1>(r.front());
	int i=0;
	vector<int> s;
	while(get<1>(r[i])>=_c)
	{
		//cout<<"["<<get<0>(r[i])<<","<<get<1>(r[i])<<"]\t";
		s.push_back(get<0>(r[i]));
		i++;
	}
	//cout<<endl;
	//return make_tuple(get<0>(r.front()),get<1>(r.front()));
	//random_shuffle(s.begin(),s.end());
	return s;
}
tuple<int,bool> testsetXor::_Choose(const string& pattern,const vector<string> hadamard,int mod)
{
	int p;
	bool reversed;
	int compatibiliry=-1;
	for(uint32_t i=0;i<hadamard.size();i++)
	{
		int t;
		t=_CmpString(pattern,hadamard[i],mod,[](const char& ch1,const char& ch2){
			if(ch1=='X'||ch1==ch2)return 1;
			return 0;});
			if(t>compatibiliry)
			{
				compatibiliry=t;
				reversed=false;
				p=i;
			}
			t=_CmpString(pattern,hadamard[i],mod,[](const char& ch1,const char& ch2){
				if(ch1=='X'||ch1!=ch2)return 1;
				return 0;});
				if(t>compatibiliry)
				{
					compatibiliry=t;
					reversed=true;
					p=i;
				}
	}
	//cout<<"["<<p<<","<<reversed<<"]\t";
	return make_tuple(p,reversed);
}
//
//#define xyl_debug
const int  reorder_times=10000;
vector<vector<int>> testsetXor_vertical::_ChooseSequence_xyl(vector<string>& _set,\
const vector<string>& hadamard)
{
	vector<vector<int>> ret;
	for(uint32_t loop=0;loop<reorder_times;++loop)
	{
	//	cout<<"loop:"<<loop<<endl;
#ifdef xyl_debug
	cout<<"\n----LOOP"<<loop<<"----"<<endl;
	cout<<"[Test set]"<<endl;
		char sa[100];
		sprintf(sa,"vec%d",loop);
	ofstream vec(sa);
	for(int i=0;i<_set.front().size();++i)
	{
		for(int j=0;j<_set.size();j++)
		{
	//	if(j%5==0)cout<<' ';
		vec<<_set[j][i];
		}
		vec<<endl;
	}
#endif
		vector<int> choosed;
		vector<vector<int>> cost;
		int t=0;
		for(auto &str:_set)
		{
			choosed.push_back(_Choose(str,hadamard).at(0));
	//		cout<<choosed.back()<<' ';
			#ifdef xyl_debug
			int c=choosed.back();
			for(int m=0;m<str.size();++m)
			{
			char xx;
			if(c<hadamard.size())
			xx=hadamard[c][m%hadamard.size()];
			else
			xx=hadamard[c-hadamard.size()][m%hadamard.size()]^1;
				if(str[m]!='X'&&str[m]!=xx)
					t++;
			}
			#endif
		}
		#ifdef xyl_debug
		//output hadamard
		cout<<"[Hadamard]"<<endl;
		char ss[100];
		sprintf(ss,"hdm%d",loop);
		ofstream hdm(ss);
		for(int i=0;i<_set.front().size();i++)
		{
			for(int j=0;j<_set.size();j++)
			{
			//	if(j%5==0)cout<<' ';
				char c;
				int cz=choosed[j];
				if(cz<hadamard.size())
					c=hadamard[cz][i%hadamard.size()];
				else
					c=hadamard[cz-hadamard.size()][i%hadamard.size()]^1;
				hdm<<c;
			}
			hdm<<endl;
		}
		cout<<"<Num of '1'>\t"<<t<<endl;
//		cout<<"cost";
//		for(int i=0;i<_set.front().size();i++)
//			cout<<"\tvec"<<i;
//		cout<<endl;
		#endif
	//	cout<<endl;
		int pattern_num=_set.front().size();
		for(int i=0;i<pattern_num;++i)
		{
		#ifdef xyl_debug
	//	cout<<"hdm"<<i<<'\t';
		#endif
	//	cout<<"i="<<i<<endl;
			vector<int> h;
			for(int j=0;j<pattern_num;++j)
			{
	//		cout<<"j="<<j<<endl;
				int sum=0;
				for(int k=0;k<_set.size();++k)
				{
					char c;
					int x=choosed[k];
					if(x>=hadamard.size())
						c=hadamard[x-hadamard.size()][i%hadamard.size()]^1;
					else 
						c=hadamard[x][i%hadamard.size()];
					if(_set[k][j]!='X'&&_set[k][j]!=c)
						sum++;
				}
				h.push_back(sum);
				#ifdef xyl_debug
	//			cout<<sum<<'\t';
				#endif
			}
			cost.push_back(h);
			#ifdef xyl_debug
	//		cout<<endl;
			#endif
		}	
		extern vector<int> xyl(vector<vector<int>>& );
		vector<int> porder=xyl(cost);
		int _cs=0;
		int _ns=0;
		for(int i=0;i<cost.size();++i)
		{
			_cs+=cost[i][i];
			_ns+=cost[porder[i]][i];
		}
		if(_cs==_ns)
		{
			cout<<"loop:"<<loop+1<<endl;
			break;
		}
		#ifdef xyl_debug
		cout<<"orign cost:"<<_cs<<endl;
		cout<<"new cost:"<<_ns<<endl;
		cout<<"[XIONYAYI choosed]"<<endl;
		for(auto x:porder)cout<<x<<' ';
		cout<<endl;
		#endif
		auto myset=_set;
		for(int i=0;i<myset.size();++i)
			for(int j=0;j<myset[i].size();++j)
			myset[i][porder[j]]=_set[i][j];
		_set=myset;
		
	}
	#ifdef xyl_debug
	cout<<endl;
	#endif
	for(auto &str:_set)
	{
		ret.push_back(_Choose(str,hadamard));
	}
	/*
	ofstream ts("ts");
	for(int i=0;i<_set.front().size();i++)
	{
	ts<<":";
		for(int j=0;j<_set.size();j++)
			ts<<_set[j][i];
		ts<<endl;
	}
	*/

	return ret;
}

vector<vector<int>> testsetXor_vertical::_ChooseSequence(const vector<string>& _set,\
const vector<string>& hadamard)
{
	//vector<tuple<int,bool>> ret;
	//vector<int> testsetXor::_Choose_multi(const vector<string>&_set,int p,\
//const vector<string> hadamard,int in_num)
#if 0
	vector<vector<int>> ret;
	for(auto &str:_set)
	{
		ret.push_back(_Choose(str,hadamard);
	}
#else
	vector<vector<int>> ret(_set.size());
	#pragma omp parallel for
	for(int i=0;i<_set.size();i++)
	{
		ret[i]=_Choose(_set[i],hadamard);
	}
#endif	
	//
	/*int num=log(ret.size())/log(2);
	num=1<<num;
	cout<<"num:"<<num<<endl;
	for(int i=num;i<ret.size();i++)
		ret.at(i)=ret.at(i-num);
	
	cout<<"Choose data:"<<endl;
	for(auto &u:ret)
	{
		for(auto &v:u)
		cout<<v<<' ';
		cout<<endl;
	}*/
	/*
	int input_num=log(ret.size()*2-1)/log(2);
	int output_num=log(hadamard.size())/log(2)+1;
	int i=0;
	for(auto &e:ret)
	{
		cout<<"WHEN\"" ;
		int c=i++;
		for(int j=input_num-1;j>=0;j--)
		{
			cout<<xmap[(c>>j)&1];
		
		}
		cout<<"\"=>XO<=\"";
		//for(auto &u:e)
		//cout<<xmap[u];
		auto u=e.front();
		for(int k=output_num-1;k>=0;k--)
		cout<<xmap[(u>>k)&1];
		cout<<"\";"<<endl;
		
	}
	*/
	return ret;
}
vector<vector<int>> testsetXor_vertical::_ChooseSequence_multi(const vector<string>& _set,\
const vector<string>& hadamard,int in_num)
{
	//vector<tuple<int,bool>> ret;
	//vector<int> testsetXor::_Choose_multi(const vector<string>&_set,int p,\
//const vector<string> hadamard,int in_num)
	int size=1<<in_num;
	vector<vector<int>> ret;
	for(int i=0;i<size&&i<_set.size();i++)
	{
		ret.push_back(_Choose_multi(_set,i,hadamard,in_num));
	}
	int k=0;
	while(ret.size()!=_set.size())
		ret.push_back(ret[k++]);
	/*
	cout<<"Choose data:"<<endl;
	for(auto &u:ret)
	{
		for(auto &v:u)
		cout<<v<<' ';
		cout<<endl;
	}*/
	/*
	int input_num=log(ret.size()*2-1)/log(2);
	int output_num=log(hadamard.size())/log(2)+1;
	int i=0;
	for(auto &e:ret)
	{
		cout<<"WHEN\"" ;
		int c=i++;
		for(int j=input_num-1;j>=0;j--)
		{
			cout<<xmap[(c>>j)&1];
		
		}
		cout<<"\"=>XO<=\"";
		//for(auto &u:e)
		//cout<<xmap[u];
		auto u=e.front();
		for(int k=output_num-1;k>=0;k--)
		cout<<xmap[(u>>k)&1];
		cout<<"\";"<<endl;
		
	}*/
	
	return ret;
}
//#define XYL
unique_ptr<string> testsetXor_vertical::compress(const vector<string>& _set1,int order)
{
	//int mod=1;
	//for(int i=2;i<=order;i++)
		//mod=(mod<<1)|1;
	vector<string> hadamard=Hadamard::get(order);
	auto _set=_set1;
	#ifndef XYL
	auto seq=_ChooseSequence(_set,hadamard);
	#else
	auto seq=_ChooseSequence_xyl(_set,hadamard);
	#endif
	unique_ptr<string> _ret(new string);
	vector<string> _vstr;
	int hsize=hadamard.at(0).length();
	for(uint32_t i=0;i<_set.size();i++)
	{
		//int p=get<0>(seq.at(i));
		int p=seq[i][0];
		//bool reversed=get<1>(seq.at(i));
		int length=_set.at(i).size();
		string _s;
		for(int j=0;j<length;j++)
		{
			char _c=_set.at(i).at(j);
			/*
			if(_c=='X')
				if(p<hadamard.size())
					_s.push_back(hadamard.at(p).at(j%hsize));
				else
					if(hadamard.at(p-hadamard.size()).at(j%hsize)=='0')
						_s.push_back('1');
					else
					_s.push_back('0');
			else
				_s.push_back(_c);
			*/
			if(_c=='X')
			{
				_s.push_back('X');
				continue;
			}
			if(p<hadamard.size())
			if(hadamard.at(p).at(j%hsize)==_c)
					_s.push_back('0');
				else
					_s.push_back('1');
			else
			if(hadamard.at(p-hadamard.size()).at(j%hsize)!=_c)
					_s.push_back('0');
				else
				_s.push_back('1');
			
		}
		_vstr.push_back(_s);
	}
	//
	int c1=_vstr.size();
	int r1=_vstr.back().size();
	int r2=_vstr.front().size()-r1;
	int k;
	for(k=0;k<_vstr.size();k++)
		if(_vstr.at(k).size()!=r1+r2)
			break;
	int c2=k;
		
	/*for(uint32_t i=0;i<r1;i++)
	{
		for(uint32_t j=0;j<c1;j++)
		{
			//_ret->push_back(_vstr.at(j).at(i));
			//if(_vstr.at(j).at(i)=='1')
			cout<<_vstr.at(j).at(i);
			//else cout<<' ';
		}
		cout<<endl;
	}
	for(uint32_t i=0;i<r2;i++)
	{
		for(uint32_t j=0;j<c2;j++)
		{
			//_ret->push_back(_vstr.at(j).at(r1+i));
			//if(_vstr.at(j).at(i)=='1')
			cout<<_vstr.at(j).at(i+r1);
			//else cout<<' ';
		}
		cout<<endl;
	}
	*/
	if(r2==0)
	{
		for(int i=0;i<_vstr.front().size();i++)
			for(int j=0;j<_vstr.size();j++)
				_ret->push_back(_vstr.at(j).at(i));
	}
	else{
	int _size=c1*(r1/r2)+c2;		
	//cout<<"size:"<<_size<<","<<r2<<endl;
	for(int i=0;i<r2;i++)
	{
		for(int j=0;j<_size;j++)
		{
			_ret->push_back(_vstr.at(j%c1).at(i+(j/c1)*r2));
			//cout<<_ret->back();
		}
		//cout<<endl;
	}}
	return _ret;
}
unique_ptr<string> testsetXor_vertical::compress_multi(const vector<string>& _set,int order,\
int in_num)
{
	//int mod=1;
	//for(int i=2;i<=order;i++)
		//mod=(mod<<1)|1;
	vector<string> hadamard=Hadamard::get(order);
	auto seq=_ChooseSequence_multi(_set,hadamard,in_num);
	unique_ptr<string> _ret(new string);
	vector<string> _vstr;
	int hsize=hadamard.at(0).length();
	for(uint32_t i=0;i<_set.size();i++)
	{
		//int p=get<0>(seq.at(i));
		int p=seq[i][0];
		//bool reversed=get<1>(seq.at(i));
		int length=_set.at(i).size();
		string _s;
		for(int j=0;j<length;j++)
		{
			char _c=_set.at(i).at(j);
			if(_c=='X')
			{
				_s.push_back('X');
				continue;
			}
			if(p<hadamard.size())
			if(hadamard.at(p).at(j%hsize)==_c)
					_s.push_back('0');
				else
					_s.push_back('1');
			else
			if(hadamard.at(p-hadamard.size()).at(j%hsize)!=_c)
					_s.push_back('0');
				else
				_s.push_back('1');
		}
		_vstr.push_back(_s);
	}
	//
	int c1=_vstr.size();
	int r1=_vstr.back().size();
	int r2=_vstr.front().size()-r1;
	int k;
	for(k=0;k<_vstr.size();k++)
		if(_vstr.at(k).size()!=r1+r2)
			break;
	int c2=k;
		
	/*for(uint32_t i=0;i<r1;i++)
	{
		for(uint32_t j=0;j<c1;j++)
		{
			//_ret->push_back(_vstr.at(j).at(i));
			//if(_vstr.at(j).at(i)=='1')
			cout<<_vstr.at(j).at(i);
			//else cout<<' ';
		}
		cout<<endl;
	}
	for(uint32_t i=0;i<r2;i++)
	{
		for(uint32_t j=0;j<c2;j++)
		{
			//_ret->push_back(_vstr.at(j).at(r1+i));
			//if(_vstr.at(j).at(i)=='1')
			cout<<_vstr.at(j).at(i+r1);
			//else cout<<' ';
		}
		cout<<endl;
	}
	*/
	if(r2==0)
	{
		for(int i=0;i<_vstr.front().size();i++)
			for(int j=0;j<_vstr.size();j++)
				_ret->push_back(_vstr.at(j).at(i));
	}
	else{
	int _size=c1*(r1/r2)+c2;		
	//cout<<"size:"<<_size<<","<<r2<<endl;
	for(int i=0;i<r2;i++)
	{
		for(int j=0;j<_size;j++)
		{
			_ret->push_back(_vstr.at(j%c1).at(i+(j/c1)*r2));
			cout<<_ret->back();
		}
		cout<<endl;
	}}
	return _ret;
}

unique_ptr<string> testsetXor_vertical::compress(const vector<string>& _set,int order,int in_num)
{
	int length=1<<in_num;
	if(length>_set.size())
		throw msg("in_num:too large");
	vector<string> set(length);
	for(int i=0;i<_set.size();i++)
		set.at(i%length)+=_set.at(i);
	return compress(set,order);	
}
unique_ptr<string> testsetXor_vertical::compress_lfsr(const vector<string>& _set,int order)
{
	//int mod=1;
	//for(int i=2;i<=order;i++)
		//mod=(mod<<1)|1;
	vector<uint8_t> _lfsr=LFSR::get(order);//_lfsr.push_back(0);
	vector<string> lfsr;
	for(int i=0;i<_lfsr.size();i++)
	{
		string _s;
		for(int j=0;j<_lfsr.size();j++)
			_s.push_back(xmap[_lfsr[(i+j)%_lfsr.size()]]);
		lfsr.push_back(_s);
	}
	//vector<string> hadamard=Hadamard::get(order);
	auto seq=_ChooseSequence(_set,lfsr);
	unique_ptr<string> _ret(new string);
	vector<string> _vstr;
	int hsize=lfsr.at(0).length();
	for(uint32_t i=0;i<_set.size();i++)
	{
		//int p=get<0>(seq.at(i));
		int p=seq[i][0];
		//bool reversed=get<1>(seq.at(i));
		int length=_set.at(i).size();
		string _s;
		for(int j=0;j<length;j++)
		{
			char _c=_set.at(i).at(j);
			if(_c=='X')
			{
				_s.push_back('X');
				continue;
			}
			if(p<lfsr.size())
			if(lfsr.at(p).at(j%hsize)==_c)
					_s.push_back('0');
				else
					_s.push_back('1');
			else
			if(lfsr.at(p-lfsr.size()).at(j%hsize)!=_c)
					_s.push_back('0');
				else
				_s.push_back('1');
		}
		_vstr.push_back(_s);
	}
	for(uint32_t i=0;i<_vstr.front().length();i++)
	{
		for(uint32_t j=0;j<_vstr.size();j++)
		{
			_ret->push_back(_vstr.at(j).at(i));
			//if(_vstr.at(j).at(i)=='1')
			//cout<<_vstr.at(j).at(i);
			//else cout<<' ';
		}
		//cout<<endl;
	}
	return _ret;
}

vector<vector<uint8_t>> testsetXor_vertical::choose(const vector<string>& _set,int order)
{
	vector<string> hadamard=Hadamard::get(order);
	vector<vector<int>> seq=_ChooseSequence(_set,hadamard);
	vector<vector<vector<uint8_t>>> merge;
	//cout<<"merged data:"<<endl;
	for(auto &e:seq)
	{
		vector<vector<uint8_t>> t;
		for(auto &num:e)
		{
			vector<uint8_t> x(order+1);
			for(int i=0;i<=order;i++)
			{
				x[i]=num&1;
				num>>=1;
			}
			t.push_back(x);
		}
		merge.push_back(merge_number(t));
	}
	//cout<<"begin:"<<endl;
	//
	//begin choose
	int input_num=log(merge.size()*2-1)/log(2);
	vector<vector<uint8_t>> ret;
	//cout<<"size:"<<merge.size()<<endl;
	for(int i=0;i<merge.size();i++)
	{	//cout<<i<<endl;
		vector<vector<uint8_t>> &cur=merge[i];
		if(cur.size()==1)
			ret.push_back(cur.front());
		else
		{
			vector<int> c(cur.size(),0);
			for(int j=0;j<input_num;j++)//neibor
			{
				int p=i^(1<<j);//flip a bit
				if(p>=merge.size())continue;
				//cout<<"p="<<p<<endl;
				for(int m=0;m<cur.size();m++)//who
				{
					vector<uint8_t> &x=merge[p].front();
					for(int k=0;k<x.size();k++)
					if(cur[m][k]^x[k]!=1)
					c[m]++;
				}
			}
			//cout<<"cur size:"<<cur.size()<<endl;
			int _m=0;
			for(int i=1;i<c.size();i++)
				if(c[_m]<c[i])
					_m=i;
			ret.push_back(cur[_m]);
		}
	}					
	//print
	cout<<"Result\nnum:"<<ret.size()<<endl;
	int i=0;
	for(auto &e:ret)
	{
		cout<<"WHEN\"" ;
		int c=i++;
		for(int j=input_num-1;j>=0;j--)
		{
			cout<<xmap[(c>>j)&1];
		
		}
		cout<<"\"=>XO<=\"";
		for(auto &u:e)
		cout<<xmap[u];
		cout<<"\";"<<endl;
	}
	return ret;
}
vector<vector<uint8_t>> testsetXor_vertical::choose_multi(const vector<string>& _set,int order,int in_num)
{
	vector<string> hadamard=Hadamard::get(order);
	vector<vector<int>> seq=_ChooseSequence_multi(_set,hadamard,in_num);
	vector<vector<vector<uint8_t>>> merge;
	//cout<<"merged data:"<<endl;
	for(auto &e:seq)
	{
		vector<vector<uint8_t>> t;
		for(auto &num:e)
		{
			vector<uint8_t> x(order+1);
			for(int i=0;i<=order;i++)
			{
				x[i]=num&1;
				num>>=1;
			}
			t.push_back(x);
		}
		merge.push_back(merge_number(t));
	}
	//cout<<"begin:"<<endl;
	//
	//begin choose
	//int input_num=log(merge.size()*2-1)/log(2);
	int input_num=in_num;
	vector<vector<uint8_t>> ret;
	//cout<<"size:"<<merge.size()<<endl;
	for(int i=0;i<merge.size();i++)
	{	//cout<<i<<endl;
		vector<vector<uint8_t>> &cur=merge[i];
		if(cur.size()==1)
			ret.push_back(cur.front());
		else
		{
			vector<int> c(cur.size(),0);
			for(int j=0;j<input_num;j++)//neibor
			{
				int p=i^(1<<j);//flip a bit
				if(p>=merge.size())continue;
				//cout<<"p="<<p<<endl;
				for(int m=0;m<cur.size();m++)//who
				{
					vector<uint8_t> &x=merge[p].front();
					for(int k=0;k<x.size();k++)
					if(cur[m][k]^x[k]!=1)
					c[m]++;
				}
			}
			//cout<<"cur size:"<<cur.size()<<endl;
			int _m=0;
			for(int i=1;i<c.size();i++)
				if(c[_m]<c[i])
					_m=i;
			ret.push_back(cur[_m]);
		}
	}					
	//print
	cout<<"Result\nnum:"<<ret.size()<<endl;
	int size=1<<in_num;
	int i=0;
	for(int x=0;x<size;x++)
	{
		auto &e=ret[x];
		cout<<"WHEN\"" ;
		int c=i++;
		for(int j=input_num-1;j>=0;j--)
		{
			cout<<xmap[(c>>j)&1];
		
		}
		cout<<"\"=>XO<=\"";
		for(auto &u:e)
		cout<<xmap[u];
		cout<<"\";"<<endl;
	}
	return ret;
}
vector<vector<uint8_t>> testsetXor_vertical::choose(const vector<string>& _set,int order,int in_num)
{
	int length=1<<in_num;
	if(length>_set.size())
		throw msg("in_num:too large");
	vector<string> set(length);
	for(int i=0;i<_set.size();i++)
		set.at(i%length)+=_set.at(i);
	return choose(set,order);
}	

vector<vector<uint8_t>> testsetXor_vertical::choose2(const vector<string>& _set,int order)
{
	//cout<<"begin.."<<endl;
	vector<string> hadamard=Hadamard::get(order);
	vector<vector<int>> seq=_ChooseSequence(_set,hadamard);
	list<tuple<int,vector<int>>> seqList;
	for(int i=0;i<seq.size();i++)
		seqList.emplace_back(i,seq.at(i));
	vector<int> sel(seq.size());
	vector<int> symbol_num(1<<(order+1));
	//cout<<"symbol_size:"<<symbol_num.size()<<endl;
	//for(auto &u:seqList)cout<<get<0>(u)<<endl;
	while(!seqList.empty())
	{
		fill(symbol_num.begin(),symbol_num.end(),0);
		auto iter=seqList.begin();
		for( ;iter!=seqList.end();++iter)
		{	
			//cout<<"dddd"<<endl;
			for(auto &u:get<1>(*iter))
			{
				//cout<<u<<" ";
				symbol_num.at(u)++;
			}	
			//cout<<"xxx"<<endl;	
			if(get<1>(*iter).size()==1)
				break;
				//cout<<"yyy"<<endl;
		}
		int sel_symbol;
		if(iter==seqList.end())
		{
			sel_symbol=max_element(symbol_num.begin(),symbol_num.end())-symbol_num.begin();
		}
		else
			sel_symbol=get<1>(*iter).front();
		//cout<<sel_symbol<<endl;
		//
		//cout<<"zzz"<<endl;
		for(auto u=seqList.begin();u!=seqList.end();)
		{
			bool erase_cur=false;
			for(auto v=get<1>(*u).begin();v!=get<1>(*u).end();++v)
				if(*v==sel_symbol)
				{
					sel.at(get<0>(*u))=sel_symbol;
					u=seqList.erase(u);
					erase_cur=true;
					break;
				}
				if(!erase_cur)
					++u;
		}
		//cout<<"$"<<seqList.size()<<endl;
	}
	//print sel (not include X)
	cout<<"[select min_num result]"<<endl;
	//cout<<"sel size:"<<sel.size()<<endl;
	for(auto &x:sel)
		cout<<x<<'\t';
	//cout<<"\nsel end."<<endl;
	//vector<vector<uint8_t>> g;
	//return g;
	vector<vector<uint8_t>> merge;
	//cout<<"merged data:"<<endl;
	int i=0;
	for(auto &e:seq)
	{
		vector<vector<uint8_t>> t;
		for(auto &num:e)
		{
			vector<uint8_t> x(order+1);
			for(int i=0;i<=order;i++)
			{
				x[i]=num&1;
				num>>=1;
			}
			t.push_back(x);
		}
		//
		vector<uint8_t> x(order+1);
		int y=sel[i++];
		for(int i=0;i<=order;i++)
		{
			x[i]=y&1;
			y>>=1;
		}
		merge.push_back(merge_number(t,x));
	}
	//cout<<"begin:"<<endl;
	//
	//begin choose
	int input_num=log(merge.size()*2-1)/log(2);
	//vector<vector<uint8_t>> ret;
				
	//print
	cout<<"\nResult\nnum:"<<merge.size()<<endl;
	i=0;
	for(auto &e:merge)
	{
		cout<<"WHEN\"" ;
		int c=i++;
		for(int j=input_num-1;j>=0;j--)
		{
			cout<<xmap[(c>>j)&1];
		
		}
		cout<<"\"=>XO<=\"";
		for(auto &u:e)
		cout<<xmap[u];
		cout<<"\";"<<endl;
	}
	return merge;
}
		
					
vector<tuple<int,bool>> testsetXor_horizontal::_ChooseSequence(const string& _set,const vector<string>& hadamard,int L)
{
	vector<tuple<int,bool>> ret;
	for(uint_fast32_t i=0;i<_set.length();i+=L)
	{
		//int dis=min(L,(int)(_set.length()-i));
		ret.push_back(_Choose(_set.substr(i,L),hadamard,hadamard.size()-1));
	}
	return ret;
}
//todo
unique_ptr<string> testsetXor_horizontal::compress(const string& _set,int order,int L)
{
	vector<string> hadamard=Hadamard::get(order);
	auto seq=_ChooseSequence(_set,hadamard,L);
	//cout<<seq.size()<<" "<<_set.size()/L<<endl;
	unique_ptr<string> _ret(new string);
	for(uint32_t i=0;i<_set.size();i+=L)
	{
		int p=get<0>(seq.at(i/L));
		bool reversed=get<1>(seq.at(i/L));
		//int dis=min(L,(int)(_set.length()-i));
		string substr=_set.substr(i,L);
		//cout<<substr.size()<<endl;
		for(uint_fast32_t j=0;j<substr.length();j++)
		{
			char _c=substr.at(j);
			int hsize=hadamard.at(p).length();
			if(!reversed)
				if(_c=='X'||_c==hadamard.at(p).at(j%hsize))
					_ret->push_back('0');
				else
					_ret->push_back('1');
			else
				if(_c=='X'||_c!=hadamard.at(p).at(j%hsize))
					_ret->push_back('0');
				else
					_ret->push_back('1');
		}
	}
	//cout<<endl;
	//cout<<*_ret<<endl;
	return _ret;
}
